#include <stdio.h>
#include <stdlib.h>

void merge(int* arr, int left, int mid, int right, int* tem) 
{
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;

    while (begin1 <= end1 && begin2 <= end2) 
    {
        if (arr[begin1] < arr[begin2]) 
        {
            tem[index++] = arr[begin1++];
        }
        else 
        {
            tem[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1) 
    {
        tem[index++] = arr[begin1++];
    }

    while (begin2 <= end2) 
    {
        tem[index++] = arr[begin2++];
    }

    for (int i = left; i <= right; i++) 
    {
        arr[i] = tem[i];
    }
}

void mergesort(int* arr, int n) 
{
    int* tem = (int*)malloc(n * sizeof(int));
    if (tem == NULL) 
    {
        return;
    }
    for (int gap = 1; gap < n; gap *= 2) 
    {
        for (int i = 0; i < n; i += 2 * gap) 
        {
            int left = i;
            int mid = i + gap - 1;
            int right = i + 2 * gap - 1;
            if (mid >= n) 
            {
                mid = n - 1;
            }
            if (right >= n) 
            {
                right = n - 1;
            }
            if (left < right) 
            {
                merge(arr, left, mid, right, tem);
            }
        }
    }

    free(tem);
}

int main() 
{
    int arr[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    mergesort(arr, n);

    for (int i = 0; i < n; i++) 
    {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}